package 剑指offer.堆栈队列;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 给出一个数组和窗口大小，请找出所有窗口内的最大值
 *
 * 窗口每次往下移动一个元素后，会得到新的窗口，不断的会有新的窗口产生
 * 求的就是各个窗口里面的最大值
 */
public class 第59题队列的最大值 {


    public static ArrayList<Integer> maxInWindows(int[] num, int size) {

        ArrayList<Integer> ans = new ArrayList<>();
        if (num.length == 0 || size <= 0) {
            return ans;
        }
        ArrayQueue<Integer> queue = new ArrayQueue<>(size);
        for (int i = 0; i <= num.length - size; i++) {
            // 先将窗口填满
            if (size > 0) {
                queue.add(num[i]);
                size--;
                continue;
            }

            // 然后找出窗口里面的最大值
            Integer max = findMaxValue(queue);
            ans.add(max);
            // 然后移动窗口
            queue.remove(0);
            if (i < num.length) {
                queue.add(num[i]);
            }
        }
        return ans;
    }

    public static Integer findMaxValue(ArrayQueue<Integer> queue) {
        Iterator<Integer> it = queue.iterator();
        Integer ans = null;
        while (it.hasNext()) {
            if (ans == null) {
                ans = it.next();
            } else {
                ans = Math.max(ans, it.next());
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
        int size = 3;
        maxInWindows(num, size).forEach(e -> System.out.println(e));
    }
}
